'''
https://leetcode.cn/problems/count-the-number-of-good-subarrays/?envType=daily-question&envId=2025-04-16
'''
from collections import defaultdict
from typing import List


class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        cnt = defaultdict(int)
        n = len(nums)
        l, r = 0, 0
        curk = 0
        res = 0
        while l < n:
            while r < n and curk < k:
                cnt[nums[r]] += 1
                curk += cnt[nums[r]] - 1
                r += 1
            if curk >= k:
                res += n - r + 1

            curk -= cnt[nums[l]] - 1
            cnt[nums[l]] -= 1
            l += 1
        return res

nums = [3,1,4,3,2,2,4]
k = 2
print(Solution().countGood(nums, k))
